/*
 * @lc app=leetcode.cn id=208 lang=cpp
 * @lcpr version=30204
 *
 * [208] 实现 Trie (前缀树)
 */

// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Trie
{
// 方法一：哈希表，有几个节点就存几个
private:
    struct TrieNode
    {
        unordered_map<char, TrieNode *> children; // 子节点
        bool isEnd;                               // 是否是一个单词的结尾

        TrieNode() : isEnd(false) {}
    };

    TrieNode *root; // 根节点

public:
    Trie()
    {
        root = new TrieNode(); // 初始化根节点
    }

    void insert(string word)
    {
        TrieNode *node = root;
        for (char c : word)
        {
            if (!node->children.count(c))
            {
                node->children[c] = new TrieNode(); // 如果没有子节点，创建新节点
            }
            node = node->children[c]; // 移动到子节点
        }
        node->isEnd = true; // 标记单词结束
    }

    bool search(string word)
    {
        TrieNode *node = root;
        for (char c : word)
        {
            if (!node->children.count(c))
            {
                return false; // 如果路径不存在，返回 false
            }
            node = node->children[c]; // 移动到子节点
        }
        return node->isEnd; // 检查是否是单词的结尾
    }

    bool startsWith(string prefix)
    {
        TrieNode *node = root;
        for (char c : prefix)
        {
            if (!node->children.count(c))
            {
                return false; // 如果路径不存在，返回 false
            }
            node = node->children[c]; // 移动到子节点
        }
        return true; // 只需判断路径是否存在
    }
/* 数组存储26个节点
private:
    struct TrieNode {
        vector<TrieNode*> children; // 子节点
        bool isEnd;                 // 是否是一个单词的结尾

        TrieNode() : children(26, nullptr), isEnd(false) {}
    };
    typedef TrieNode Node;

    Node* root; // 根节点
public:
    Trie() { root = new Node(); }

    void insert(string word) {
        Node* cur = root;
        for (char c : word) {
            int index = c - 'a';
            if (cur->children[index] == nullptr) {
                cur->children[index] = new Node();
            }
            cur = cur->children[index];
        }
        cur->isEnd = true;
    }

    bool search(string word) {
        Node* cur = root;
        for (char c : word) {
            int index = c - 'a';
            if (cur->children[index] == nullptr)
            {
                return false;
            }
            cur = cur->children[index];
        }
        return cur->isEnd;
    }

    bool startsWith(string prefix) {
        Node* cur = root;
        for(char c : prefix)
        {
            int index = c - 'a';
            if (cur->children[index] == nullptr)
            {
                return false;
            }
            cur = cur->children[index];
        }
        return true;
    }
*/
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */
// @lc code=end
